class Solution:
    def maxSumTwoNoOverlap(self, A: list, L: int, M: int) -> int:
        prefix = [0 for _ in range(len(A))]
        s = 0
        cur_max = 0
        s_array = [0 for _ in range(len(A) + 1)]
        for i in range(len(A)):
            s += A[i]
            s_array[i + 1] = s
            if i + 1 < M:
                continue
            prefix[i] = max(cur_max, s_array[i + 1] - s_array[i + 1 - M])
            cur_max = prefix[i]

        suffix = [0 for _ in range(len(A))]
        s = 0
        cur_max = 0
        s_array = [0 for _ in range(len(A) + 1)]
        for i in range(len(A) - 1, -1, -1):
            s += A[i]
            s_array[i] = s
            if i + M >= len(s_array):
                continue
            suffix[i] = max(cur_max, s_array[i] - s_array[i + M])
            cur_max = suffix[i]

        s = 0
        cur_max = 0
        s_array = [0 for _ in range(len(A) + 1)]
        res = 0
        for i in range(len(A)):
            s += A[i]
            s_array[i + 1] = s
            if i + 1 < L:
                continue
            start = i + 1 - L
            end = i + 1
            cur_sum = s_array[end] - s_array[start]
            pf = prefix[start - 1] if start - 1 >= 0 else 0
            sf = suffix[end] if end < len(suffix) else 0
            res = max(res, cur_sum + pf, cur_sum + sf)

        return res


if __name__ == "__main__":
    print(Solution().maxSumTwoNoOverlap([3, 4, 0, 1, 2], 1, 2))
